package io.gitee.wiqer.medium;

import io.gitee.wiqer.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class SolutionNC8_PathSum {
    /**
     *
     * @param root TreeNode类
     * @param sum int整型
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        getRes(root,sum,res,0,new Stack<Integer>());
        return res;
    }
    public void getRes(TreeNode root, int sum ,ArrayList<ArrayList<Integer>> res, int curr, Stack<Integer> currNums){
        if(null==root)
            return;
        if(null == root.left && null == root.right){
            curr+=root.val;
            currNums.push(root.val);
            if(sum==curr){
                if(!currNums.isEmpty()){
                    ArrayList<Integer> list = new ArrayList(Arrays.asList(currNums.toArray(new Integer[0])));
                    res.add(list);
                }
            }
            currNums.pop();
            return;
        }
        currNums.push(root.val);
        getRes(root.left ,sum,res,curr+root.val,currNums);
        getRes(root.right,sum,res,curr+root.val,currNums);
        currNums.pop();
    }
}
